#include <vector>
using namespace std;
/*
 * @lc app=leetcode.cn id=153 lang=cpp
 *
 * [153] 寻找旋转排序数组中的最小值
 */

// @lc code=start
class Solution {
public:
    int findMin(vector<int>& nums) {
        int sz = nums.size();
        auto get = [&](int idx) -> int {
            return nums[(idx + sz) % sz];
        };
        int l = 0, r = sz - 1; // [ ]
        while (l < r) {
            int middle = (r + l) / 2;
            if (get(middle) < get(middle + 1) && get(middle) < get(middle - 1)) return nums[middle];
            else if (nums[middle] >= nums[r]) {
                l = middle + 1;
            }
            else r = middle - 1;
        }
        return nums[l];
    }
};
// @lc code=end

